package com.leetcode.partition2;

/**
 * @author `RKC`
 * @date 2021/9/3 14:53
 */
public class LC134加油站 {

    public static int canCompleteCircuit(int[] gas, int[] cost) {
        return greedy2(gas, cost);
    }

    public static void main(String[] args) {
        int[] gas = {1, 2, 3, 4, 5}, cost = {3, 4, 5, 1, 2};
        System.out.println(canCompleteCircuit(gas, cost));
    }

    private static int greedy2(final int[] gas, final int[] cost) {
        int start = 0, rest = 0, run = 0;
        for (int i = 0; i < gas.length; i++) {
            int remain = gas[i] - cost[i];
            rest += remain;
            run += remain;
            if (run < 0) {           //已经跑过的路程的油量不够消耗，从i+1开始
                run = 0;
                start = i + 1;
            }
        }
        //如果rest小于0，说明所有加油站的油相加都不够消耗
        return rest < 0 ? -1 : start;
    }

    private static int greedy(int[] gas, int[] cost) {
        int currentGas = 0;         //当前剩余油量
        int minGas = Integer.MAX_VALUE;             //从起点出发，当前油量的最小值
        //默认从0加油站开始出发
        for (int i = 0; i < gas.length; i++) {
            int remain = gas[i] - cost[i];
            currentGas += remain;
            minGas = Math.min(minGas, currentGas);
        }
        if (currentGas < 0) return -1;          //加油站的所有站点的油量和不足以消耗
        if (minGas >= 0) return 0;       //0开始的加油站能够走完一圈
        //0加油站不够走完一圈，从非0节点出发，从后向前遍历，检查哪个节点能够补充好汽油
        for (int i = gas.length - 1; i >= 0; i--) {
            int remain = gas[i] - cost[i];
            minGas += remain;
            if (minGas >= 0) return i;           //找到符合条件的节点
        }
        return -1;
    }
}
